/*!
 * \file rdmaxclique.c
 *
 * \date Sep 24, 2013
 * \author Ricardo C. Corrêa (correa@lia.ufc.br)
 *
 * \brief Russian doll algorithm for maximum clique.
 */

#include <mcr.h>
#include <heap.h>
#include <stdlib.h>

static int bucketSort1(int * prio, int cmin, int cmax, int * R, int r, int dir) {
	int c = cmax - cmin + 1;
	int b[c];
	int next[r + 1];
	int v[r];
	int i;
	for (i = 0; i < c; i++)
		b[i] = r;
	for (i = 0; i < r; i++) {
		next[i] = b[prio[i] - cmin];
		b[prio[i] - cmin] = i;
		v[i] = R[i];
	}
	int j = 0, k;
	if (dir != 0)
		for (i = 0; j < r; i++) {
			k = b[i];
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
		}
	else
		for (i = c - 1; j < r; i--) {
			k = b[i];
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
		}
	return c;
}

static inline int bucketSort2(int * prio1, int * prio2, int cmin, int cmax,
		int * R, int r, int dir) {

	int inccmp(const void *a, const void *b, void * prio) {
		return ((int *) prio)[*((int *) a)] - ((int *) prio)[*((int *) b)];
	}

	int deccmp(const void *a, const void *b, void * prio) {
		return ((int *) prio)[*((int *) b)] - ((int *) prio)[*((int *) a)];
	}

	int c = cmax - cmin + 1;
	int b[c];
	int next[r + 1];
	int v[r];
	int i;
	for (i = 0; i < c; i++)
		b[i] = r;
	for (i = 0; i < r; i++) {
		next[i] = b[prio1[i] - cmin];
		b[prio1[i] - cmin] = i;
		v[i] = R[i];
	}
	int j = 0, k, l;
	if (dir != 0)
		for (i = 0; j < r; i++) {
			k = b[i];
			l = j;
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
			if (l < j)
				qsort_r(R + l, j - l, sizeof(int), inccmp, prio2);
		}
	else
		for (i = c - 1; j < r; i--) {
			k = b[i];
			l = j;
			while (k < r) {
				R[j++] = v[k];
				k = next[k];
			}
			if (l < j)
				qsort_r(R + l, j - l, sizeof(int), deccmp, prio2);
		}
	return c;
}

int decDegree(Graph * g, int * res) {
	int j;
	int maxdeg = 0, mindeg = g->n;
	int deg[g->n];
	int pos[g->n];
	for (j = 0; j < g->n; j++) {
		deg[j] = cardOfSet(neig(g, j));
		if (deg[j] > maxdeg)
			maxdeg = deg[j];
		if (deg[j] < mindeg)
			mindeg = deg[j];
		pos[j] = j;
	}

	// sorts vertices according to degrees
	bucketSort1(deg, mindeg, maxdeg, pos, g->n, 0);
	for (j = 0; j < g->n; j++)
		res[pos[j]] = j;

	return maxdeg;
}

int decExdegree(Graph * g, int * res) {
//	int u;
//	int j;
//
//	int deg[g->n];
//	int exdeg[g->n];
//	int pos[g->n];
//
//	//initializes the vector of degrees
//	int lastnode = NODEIDX(g->n-1);
//	int maxdeg = 0, mindeg = g->n;
//	for (j = 0; j < g->n; j++) {
//		deg[j] = cardOfSet(neig(g, j));
//		if (deg[j] > maxdeg)
//			maxdeg = deg[j];
//		if (deg[j] < mindeg)
//			mindeg = deg[j];
//		pos[j] = j;
//	}

	int j;

	//initializes the vector of degrees
	int maxdeg = 0, mindeg = g->n;
	int * deg = calloc(g->n << 2, sizeof(int));
	int * exdeg = deg + g->n;
	int * pos = exdeg + g->n;

	for (j = 0; j < g->n; j++) {
		deg[j] = cardOfSet(neig(g, j));
		if (deg[j] > maxdeg)
			maxdeg = deg[j];
		if (deg[j] < mindeg)
			mindeg = deg[j];
		pos[j] = j;
	}



//
//	//initializes the vector of ex-degrees
//	int nodeidx;
//	for (j = 0; j < g->n; j++) {
//		exdeg[j] = 0;
//		nodeidx = 0;
//		u = NODELEAST(NEIG(g, j)[nodeidx]);
//		while (u < 0 && nodeidx < lastnode)
//			u = NODELEAST(NEIG(g, j)[++nodeidx]);
//		while (u >= 0) {
//			exdeg[j] += deg[NELEM(nodeidx) + u];
//			u = NODENEXTLEAST(NEIG(g, j)[nodeidx],u);
//			while (u < 0 && nodeidx < lastnode)
//				u = NODELEAST(NEIG(g, j)[++nodeidx]);
//		}
//	}



	//initializes the vector of ex-degrees
	Node node;
	for (j = 0; j < g->n; j++) {
		exdeg[j] = 0;
		BitMap const * jg = neig(g, j);
		for (begin(jg, &node); !end(&node); next(&node))
			exdeg[j] += deg[getElement(&node)] - 1;
	}

	// sorts vertices according to degrees
	bucketSort2(deg, exdeg, mindeg, maxdeg, pos, g->n, 0);
	for (j = 0; j < g->n; j++)
		res[pos[j]] = j;

	free(deg);

	return maxdeg;
}

int heapMcr(Graph * g, int * ret) {
	int u;
	int j;

	int * deg = calloc(g->n << 2, sizeof(int));
	int * exdeg = deg + g->n;
	int * pos = exdeg + g->n;
	int * res = pos + g->n;

	//initializes the vector of degrees
	int maxdeg = 0, mindeg = g->n;
	for (j = 0; j < g->n; j++) {
		deg[j] = cardOfSet(neig(g, j));
		if (deg[j] > maxdeg)
			maxdeg = deg[j];
		if (deg[j] < mindeg)
			mindeg = deg[j];
		res[j] = j;
		pos[j] = j;
	}

	//initializes the vector of ex-degrees
	Node node;
	for (j = 0; j < g->n; j++) {
		exdeg[j] = 0;
		BitMap const * jg = neig(g, j);
		for (begin(jg, &node); !end(&node); next(&node))
			exdeg[j] += deg[getElement(&node)] - 1;
	}

	int deccmp(const void *a, const void *b) {
		int ret = deg[*((int *) a)] - deg[*((int *) b)];
		return ret == 0 ? exdeg[*((int *) a)] - exdeg[*((int *) b)] : ret;
	}

	int hash(const void * x) {
		return *((int *) x);
	}

	heapify_a(pos, g->n, sizeof(int), deccmp, res, hash);

	int x, v, w;
	BitMap * bitm = newBitMapVector(3,g->n);
	BitMap * bitvector = bitm;
	addAllElements(bitvector);

	BitMap * interv = ++bitm;
	BitMap * interu = ++bitm;

//	printf("[");
	for (x = 0, j = g->n; x < g->n; x++) {
		v = pos[0];
		setElement(&node, v);
		ret[v] = --j;
		heappoll_a(pos, g->n - x, sizeof(int), deccmp, res, hash);

//		printf(" %d:%d:%d:%d", v,pos[v],deg[v],exdeg[v]);
//		fflush(NULL);

		delElement(bitvector, &node);
		intersectOf(interv, bitvector, neig(g, v));
		for (begin(interv, &node); !end(&node); next(&node)) {
			u = getElement(&node);
			deg[u]--;
			exdeg[u] -= deg[v] - 1;

			heapdown_a(pos, res[u], g->n - x - 1, sizeof(int), deccmp, res,	hash);

			Node nodeu;
			intersectOf(interu, bitvector, neig(g, u));
			for (begin(interu, &nodeu); !end(&nodeu); next(&nodeu)) {
				w = getElement(&nodeu);
				exdeg[w]--;

				heapdown_a(pos, res[w], g->n - x - 1, sizeof(int), deccmp, res,	hash);
			}
		}
	}
//	printf(" ]\n");
	freeBitMap(bitvector);
	free(deg);

	return maxdeg;
}

int listMcr(Graph * g, int * ret) {
	int u;
	int j;

	int * deg = calloc(g->n << 2, sizeof(int));
	int * exdeg = deg + g->n;
	int * nextl = exdeg + g->n;

	//initializes the vector of degrees
	int maxdeg = 0, mindeg = g->n;
	for (j = 0; j < g->n; j++) {
		deg[j] = cardOfSet(neig(g, j));
		if (deg[j] > maxdeg)
			maxdeg = deg[j];
		if (deg[j] < mindeg)
			mindeg = deg[j];
		nextl[j] = j+1;
	}

	//initializes the vector of ex-degrees
	Node node;
	for (j = 0; j < g->n; j++) {
		exdeg[j] = 0;
		for (begin(neig(g, j), &node); !end(&node); next(&node))
			exdeg[j] += deg[getElement(&node)] - 1;
	}

	int deccmp(const void *a, const void *b) {
		int ret = deg[*((int *) a)] - deg[*((int *) b)];
		return ret == 0 ? exdeg[*((int *) a)] - exdeg[*((int *) b)] : ret;
	}

	int x, v, w;
	BitMap * bitm = newBitMapVector(3,g->n);
	BitMap * bitvector = bitm;
	addAllElements(bitvector);

	BitMap * interv = bitm + 1;
	BitMap * interu = bitm + 2;

//	printf("[");
//	fflush(NULL);
	int head = 0;
	for (j = g->n - 1; j >= 0; j--) {
		u = -1;
		v = head;
		for (x = v; nextl[x] < g->n; x = nextl[x])
			if (deccmp(&nextl[x], &v) < 0) {
				u = x;
				v = nextl[x];
			}
		ret[v] = j;

		if (v == head)
			head = nextl[head];
		else
			nextl[u] = nextl[v];

//		printf(" %d:%d:%d:%d ", u,v,deg[v],exdeg[v]);
//		fflush(NULL);

		setElement(&node, v);
		delElement(bitvector, &node);
		intersectOf(interv, bitvector, neig(g, v));
		for (begin(interv, &node); !end(&node); next(&node)) {
			u = getElement(&node);
			deg[u]--;
			exdeg[u] -= deg[v] - 1;

			Node nodeu;
			intersectOf(interu, bitvector, neig(g, u));
			for (begin(interu, &nodeu); !end(&nodeu); next(&nodeu)) {
				w = getElement(&nodeu);
				exdeg[w]--;
			}
		}
	}
//	printf(" ]\n");
	freeBitMap(bitvector);
	free(deg);

	return maxdeg;
}

//int mcr(Graph * g, int * res) {
//	int nelem;
//	int nnelem;
//	int * next1; // list of keys, level 1; also used in the list of free nodes
//	int * next2; // list of keys, level 2
//	int * prev1; // list of keys, level 1; also used in the list of free nodes
//	int * prev2; // list of keys, level 2
//	int * key1; // key, level 1
//	int * first3; // first element of the associated list of level 3
//	int * node1; // node in the list of level 1
//
//	int freehead; // free nodes of the lists of degrees
//	int tailfree; // list of free nodes
//	int tail1; // list of level 1
//	int tail2; // lists of level 2
//	int head1; // head of the list of level 1
//
//	int * next3; // list of keys, level 3
//	int * prev3; // list of keys, level 3
//	int * key2; // key, level 3
//	int * node2; // node in the list of level 2
//
//	int tail3; // lists of level 3
//
//	/*! \fn void removeFree(int j)
//	 * \brief Removes a specified node from the list of free nodes
//	 *
//	 * The specified node is removed from the using the entry associated with it in the arrays
//	 * next1 and prev1. freehead is updated if necessary.
//	 *
//	 * \param j the index of the node to be removed
//	 */
//	inline void removeFree(int j) {
//		next1[prev1[j]] = next1[j];
//		prev1[next1[j]] = prev1[j];
//		if (j == freehead)
//			freehead = next1[j];
//	}
//
//	void reset() {
//		freehead = 0;
//		for (tailfree = 0; tailfree <= nnelem + 1; tailfree++) {
//			next1[tailfree] = tailfree + 1;
//			prev1[tailfree] = tailfree - 1;
//		}
//		prev1[0] = --tailfree;
//		next1[tailfree] = 0;
//		tail1 = tailfree - 1;
//		removeFree(tail1);
//		head1 = tail1;
//
//		tail2 = tail1 - 1;
//		removeFree(tail2);
//		tail3 = nelem;
//	}
//
//	void initTripleList(int n) {
//		nelem = n;
//		nnelem = 1 + (n << 1); // an index is left as sentinel
//
//		next1 = (int *) calloc((nnelem << 2) + 8 + (nnelem << 1) + 1,
//				sizeof(int));
//		next2 = next1 + nnelem + 2;
//		prev1 = next2 + nnelem + 2;
//		key1 = prev1 + nnelem + 2;
//		next3 = key1 + nnelem;
//		prev3 = next3 + n + 1;
//		key2 = prev3 + n + 1;
//		node2 = key2 + n + 1;
//
//		prev2 = prev1;
//		node1 = key1;
//		first3 = next1;
//
//		reset();
//	}
//
//	void delTripleList() {
//		free(next1);
//	}
//
//	/*! \fn	int comparKey2(int * a, int * b)
//	 * \brief Comparison function that specifies the order of level 2 according to \c key2
//	 *
//	 * The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered
//	 * to  be respectively  less  than, equal to, or greater than the second.  If two members compare as equal, their order in the
//	 * sorted array is undefined.
//	 *
//	 * This comparison function is used in functions insertLevel3Backward() and insertLevel3Forward().
//	 *
//	 * \param a first argument
//	 * \param b second argument
//	 * \return an integer less than, equal to, or greater than zero if the first argument is considered
//	 * to  be respectively  less  than, equal to, or greater than the second
//	 */
//	inline int comparKey2(int * a, int * b) {
//		return *a - *b;
//	}
//
//	/*! \fn int removeFreeHead()
//	 * \brief Removes an arbitrary node from the list of free nodes
//	 *
//	 * The returned node is removed from the head of the list. freehead is updated.
//	 *
//	 * \return a free node, if there is one, or tail12, otherwise.
//	 */
//	inline int removeFreeHead() {
//		int ret = freehead;
//
//		next1[prev1[freehead]] = next1[freehead];
//		prev1[next1[freehead]] = prev1[freehead];
//		freehead = next1[freehead];
//
//		return ret;
//	}
//
//	/*! \fn void addFreeHead(int i)
//	 * \brief Adds the specified node to the list of free nodes
//	 *
//	 * The specified node is added to the head of the list. freehead is updated accordingly.
//	 *
//	 * \param i the index of the node to be added
//	 */
//	inline void addFreeHead(int i) {
//		prev1[i] = prev1[freehead];
//		next1[prev1[freehead]] = i;
//		next1[i] = freehead;
//		prev1[freehead] = i;
//		freehead = i;
//	}
//
//	/*! \fn	int insertLevel3Forward(int j, int i)
//	 * \brief Inserts the specified node in the list of level 3 associated with node of a list of level 2 of certain key after a
//	 * specified node of level 2
//	 *
//	 * The insertion is performed in the list of level 3 of a node of level 2 *after* the specified basepoint.
//	 * This method searches for the node in the list of level 2 until a member corresponding to the specified node's key of level 2
//	 * is found or it is detected that such a member does not exist. A new node is inserted in the list of level 2 if necessary.
//	 *
//	 * Nodes at level 2 are assumed to be ordered in an ascending order of keys determined by comparKey2().
//	 *
//	 * \param j the basepoint
//	 * \param i the node to insert
//	 *
//	 * \return the node of the list of level 2 that receives the specified node of level 3
//	 */
//	inline int insertLevel3Forward(int j, int i) {
//		int h;
//		if (next2[j] != tail2) {
//			j = next2[j];
//			int c = comparKey2(&key2[first3[j]], &key2[i]);
//			while (next2[j] != tail2 && c < 0) {
//				j = next2[j];
//				c = comparKey2(&key2[first3[j]], &key2[i]);
//			}
//			if (c == 0)
//				h = j;
//			else if (next2[j] == tail2 && c < 0) {
//				h = j;
//				j = tail2;
//			} else
//				h = prev2[j];
//		} else {
//			h = j;
//			j = tail2;
//		}
//
//		if (h == j) {
//			next3[i] = first3[j];
//			prev3[first3[j]] = i;
//			node2[i] = j;
//			prev3[i] = tail3;
//			first3[j] = i;
//		} else {
//			int l = removeFreeHead();
//
//			next2[h] = l;
//			prev2[l] = h;
//			next2[l] = j;
//			prev2[j] = l;
//
//			first3[l] = i;
//			next3[i] = tail3;
//			node2[i] = l;
//			prev3[i] = tail3;
//			j = l;
//		}
//
//		return j;
//	}
//
//	/*! \fn	int insertLevel3Backward(int j, int i)
//	 * \brief Inserts the specified node in the list of level 3 associated with node of a list of level 2 of certain key after a
//	 * specified node of level 2
//	 *
//	 * The insertion is performed in the list of level 3 of a node of level 2 *after* the specified basepoint.
//	 * This method searches for the node in the list of level 2 until a member corresponding to the specified node's key of level 2
//	 * is found or it is detected that such a member does not exist. A new node is inserted in the list of level 2 if necessary.
//	 *
//	 * Nodes at level 2 are assumed to be ordered in an ascending order of keys determined by comparKey2().
//	 *
//	 * \param j the basepoint
//	 * \param i the node to insert
//	 *
//	 * \return the node of the list of level 2 that receives the specified node of level 3
//	 */
//	inline int insertLevel3Backward(int j, int i) {
//		int h, nd1 = node1[j];
//		if (prev2[j] != nd1) {
//			j = prev2[j];
//			int c = comparKey2(&key2[first3[j]], &key2[i]);
//			while (prev2[j] != nd1 && c > 0) {
//				j = prev2[j];
//				c = comparKey2(&key2[first3[j]], &key2[i]);
//			}
//			if (c == 0)
//				h = j;
//			else if (prev2[j] == nd1 && c > 0)
//				h = nd1;
//			else {
//				h = j;
//				j = next2[j];
//			}
//		} else
//			h = nd1;
//
//		if (h == j) {
//			next3[i] = first3[j];
//			prev3[first3[j]] = i;
//			node2[i] = j;
//			prev3[i] = tail3;
//			first3[j] = i;
//		} else {
//			int l = removeFreeHead();
//
//			next2[h] = l;
//			prev2[l] = h;
//			next2[l] = j;
//			prev2[j] = l;
//
//			first3[l] = i;
//			next3[i] = tail3;
//			node2[i] = l;
//			prev3[i] = tail3;
//			j = l;
//		}
//
//		return j;
//	}
//
//	/*! \fn int insertLevel1Before(int k)
//	 *
//	 * \brief Inserts a free node in the list of level 1 just before a specified node
//	 *
//	 * A free node is removed from the free list with removeFreeHead(). head1 is
//	 * updated if necessary.
//	 *
//	 * \param k the node in the list of level 1 before which the free node is inserted
//	 *
//	 * \return the node removed
//	 */
//	inline int insertLevel1Before(int k) {
//		int j = removeFreeHead();
//		next1[prev1[k]] = j;
//		prev1[j] = prev1[k];
//		prev1[k] = j;
//		next1[j] = k;
//		if (head1 == k)
//			head1 = j;
//
//		return j;
//	}
//
//	/*!	\fn int removeLevel1(int j)
//	 * \brief Removes the specified node from the list of level 1
//	 *
//	 * head1 is updated if necessary. The node returned is not added to the list of free nodes.
//	 *
//	 * \param j the node to be removed
//	 *
//	 * \return the node inserted
//	 */
//	inline int removeLevel1(int j) {
//		next1[prev1[j]] = next1[j];
//		prev1[next1[j]] = prev1[j];
//		if (j == head1)
//			head1 = next1[j];
//
//		return j;
//	}
//
//	/*! \fn int removeLevel2(int j)
//	 * \brief Removes the specified node from the list of level 2
//	 *
//	 * List of level 1 is updated if its node heading the list of level 2 conatining the specified node becomes empty.
//	 * If a node is removed from the list of level 1, then it is added
//	 * to the list of free nodes with addFreeHead().
//	 *
//	 * The node returned is not added to the list of free nodes.
//	 *
//	 * \param j the node to be removed
//	 *
//	 * \return the node removed
//	 */
//	inline int removeLevel2(int j) {
//		next2[prev2[j]] = next2[j];
//		prev2[next2[j]] = prev2[j];
//
//		if (next2[node1[j]] == tail2) {
//			removeLevel1(node1[j]);
//			addFreeHead(node1[j]);
//		}
//
//		return j;
//	}
//
//	/*! \fn	int removeLevel3Of(int j)
//	 * \brief Removes a node from the list of level 3 associated with the specified node of a list of level 2
//	 *
//	 * If the list of level 3 involved in this operation becomes empty, then the specified node is removed from its list of
//	 * level 2 and added to the list of free nodes. In this case, if the corresponding node in the list of level 1 also becomes
//	 * empty, then it is removed and added to the list of free nodes.
//	 *
//	 * \param j a node of a list of level 2
//	 *
//	 * \return the node removed
//	 */
//	inline int removeLevel3Of(int j) {
//		int i = first3[j];
//		first3[j] = next3[i];
//
//		if (first3[j] == tail3) {
//			removeLevel2(j);
//			addFreeHead(j);
//		}
//
//		return i;
//	}
//
//	/*! \fn	int removeLevel3(int i)
//	 * \brief Removes the specified node from the list of level 3
//	 *
//	 * If the list of level 3 involved in this operation becomes empty, then the corresponding node is removed from its list of
//	 * level 2 and added to the list of free nodes.
//	 *
//	 * No nodes are removed from the list of level 1.
//	 *
//	 * \param i a node of a list of level 3
//	 *
//	 * \return the node of the list of level 1 corresponding to the node of level 3 removed
//	 */
//	inline int removeLevel3(int i) {
//		int j = node2[i];
//		int ret = node1[j];
//		if (first3[j] == i) {
//			first3[j] = next3[i];
//			prev3[first3[j]] = tail3;
//			if (first3[j] == tail3) {
//				next2[prev2[j]] = next2[j];
//				prev2[next2[j]] = prev2[j];
//				addFreeHead(j);
//			}
//		} else {
//			next3[prev3[i]] = next3[i];
//			prev3[next3[i]] = prev3[i];
//		}
//
//		return ret;
//	}
//
//	inline void printLevel3(int v2) {
//		int v3 = first3[v2];
//		printf(" [key2=%d:", key2[v3]);
//		while (v3 != tail3) {
//			printf(" %d", v3);
//			v3 = next3[v3];
//		}
//		printf("]");
//	}
//
//	inline void printLevel2(int v1) {
//		printf("key1=%d", key1[v1]);
//		int v2 = next2[v1];
//		while (v2 != tail2) {
//			printLevel3(v2);
//			v2 = next2[v2];
//		}
//		printf("\n");
//	}
//
//	inline void print() {
//		int v1 = head1;
//		while (v1 != tail1) {
//			printLevel2(v1);
//			v1 = next1[v1];
//		}
//	}
//
//	int v, u;
//	int j;
//
//	//initializes the vector of degrees
//	initTripleList(g->n);
//	int lastnode = NODEIDX(g->n-1);
//	int maxdeg = 0, mindeg = g->n;
//	for (j = 0; j < g->n; j++) {
//		removeFree(j);
//		key1[j] = cardOfSet(NEIG(g, j), 0, lastnode + 1);
//		if (key1[j] > maxdeg)
//			maxdeg = key1[j];
//		if (key1[j] < mindeg)
//			mindeg = key1[j];
//		res[j] = j;
//	}
//
//	// sorts vertices according to degrees
//	bucketSort1(key1, mindeg, maxdeg, res, g->n, 1);
//
//	//initializes the vector of ex-degrees
//	int nodeidx;
//	for (j = 0; j < g->n; j++) {
//		key2[j] = 0;
//		nodeidx = 0;
//		u = NODELEAST(NEIG(g, j)[nodeidx]);
//		while (u < 0 && nodeidx < lastnode)
//			u = NODELEAST(NEIG(g, j)[++nodeidx]);
//		while (u >= 0) {
//			key2[j] += key1[NELEM(nodeidx) + u];
//			u = NODENEXTLEAST(NEIG(g, j)[nodeidx],u);
//			while (u < 0 && nodeidx < lastnode)
//				u = NODELEAST(NEIG(g, j)[++nodeidx]);
//		}
//	}
//
//	// sorts vertices according to degrees
//	head1 = res[0];
//	next1[head1] = tail1;
//	prev1[head1] = tail1;
//	next1[tail1] = head1;
//	prev1[tail1] = head1;
//	next2[head1] = tail2;
//	next2[tail1] = tail2;
//
//	int current1 = head1;
//	prev2[tail2] = current1;
//	node1[tail2] = current1;
//	v = insertLevel3Backward(tail2, res[0]);
//	node1[v] = current1;
//	for (j = 1; j < g->n; j++) {
//		if (key1[res[j]] == key1[current1])
//			addFreeHead(res[j]);
//		else {
//			next1[res[j]] = next1[current1];
//			prev1[next1[current1]] = res[j];
//			next1[current1] = res[j];
//			prev1[res[j]] = current1;
//			current1 = res[j];
//			next2[current1] = tail2;
//			v = current1;
//			prev2[tail2] = current1;
//			node1[tail2] = current1;
//		}
//		v = insertLevel3Backward(next2[v], res[j]);
//		node1[v] = current1;
//	}
//
//	//sorting
//	NODETYPE bitvector[lastnode + 1];
//	ADDALL(bitvector, lastnode+1);
//	int i = g->n;
//	while (--i >= 0) {
//		//color the first in the heap
//		v = removeLevel3Of(next2[head1]);
//		bitvector[NODEIDX(v)] = DELFROMNODE(bitvector[NODEIDX(v)], IDXINNODE(v));
//		res[v] = i; //g->n-i-1;
//
//		int unodeidx = 0;
//		int uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
//		while (uidx < 0 && unodeidx < lastnode) {
//			++unodeidx;
//			uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
//		}
//		while (uidx >= 0) {
//			int u = NELEM(unodeidx) + uidx;
//			int keyu = key1[node1[node2[u]]] - 1;
//			int wnodeidx = 0;
//			int w, y;
//			int widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
//			while (widx < 0 && wnodeidx < lastnode) {
//				++wnodeidx;
//				widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
//			}
//			while (widx >= 0) {
//				w = NELEM(wnodeidx) + widx;
//				int nd2 = node2[w];
//				int pnd2 = prev2[nd2];
//				if (first3[nd2] == w && next3[w] == tail3)
//					y = next2[nd2];
//				else
//					y = nd2;
//				int z = removeLevel3(w);
//				key2[w]--;
//				prev2[tail2] = pnd2;
//				node1[tail2] = node1[nd2];
//				y = insertLevel3Backward(y, w);
//				node1[y] = z;
//				widx =
//						NODENEXTLEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx],widx);
//				while (widx < 0 && wnodeidx < lastnode) {
//					++wnodeidx;
//					widx = NODELEAST(NEIG(g, u)[wnodeidx] & bitvector[wnodeidx]);
//				}
//			}
//
//			y = removeLevel3(u);
//			w = next1[y];
//			int s = key1[y];
//			if (next2[y] == tail2) {
//				removeLevel1(y);
//				addFreeHead(y);
//				y = w;
//			}
//			if (y == head1 || key1[prev1[y]] < s - 1) {
//				y = insertLevel1Before(y);
//				next2[y] = tail2;
//				key1[y] = s - 1;
//			} else
//				y = prev1[y];
//			w = y;
//			key2[u] -= keyu;
//			y = insertLevel3Forward(y, u);
//			node1[y] = w;
//			uidx =
//					NODENEXTLEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx],uidx);
//			while (uidx < 0 && unodeidx < lastnode) {
//				++unodeidx;
//				uidx = NODELEAST(NEIG(g, v)[unodeidx] & bitvector[unodeidx]);
//			}
//		}
//	}
//
//	delTripleList();
//	return maxdeg;
//}
